public class isMatch {
  /**
 * 判断字符串s是否能被模式p匹配
 *
 * @param s 待匹配的字符串
 * @param p 匹配模式，包含'.'和'*'两种特殊字符
 * @return 如果s能被p匹配，则返回true；否则返回false
 */
public boolean isMatch(String s, String p) {
    // m和n分别为字符串s和模式p的长度加1
    int m = s.length() + 1, n = p.length() + 1;
    // dp[i][j]表示字符串s的前i个字符能否被模式p的前j个字符匹配
    boolean[][] dp = new boolean[m][n];
    // 空字符串和空模式匹配
    dp[0][0] = true;
    // 初始化首行，处理模式p以'*'结尾的情况
    for(int j = 2; j < n; j += 2)
        dp[0][j] = dp[0][j - 2] && p.charAt(j - 1) == '*';
    // 状态转移
    for(int i = 1; i < m; i++) {
        for(int j = 1; j < n; j++) {
            // 当模式字符为'*'时
            if (p.charAt(j - 1) == '*') {
                // 情况1: '*'表示零个前面的元素
                if (dp[i][j - 2]) dp[i][j] = true;                                            // 1.
                // 情况2: '*'表示一个或多个前面的元素，且s的当前字符与p的前一个字符相同
                else if (dp[i - 1][j] && s.charAt(i - 1) == p.charAt(j - 2)) dp[i][j] = true; // 2.
                // 情况3: '*'表示一个或多个前面的元素，且p的前一个字符为'.'
                else if (dp[i - 1][j] && p.charAt(j - 2) == '.') dp[i][j] = true;             // 3.
            } else {
                // 当模式字符不为'*'时
                // 情况1: s和p的当前字符相同
                if (dp[i - 1][j - 1] && s.charAt(i - 1) == p.charAt(j - 1)) dp[i][j] = true;  // 1.
                // 情况2: p的当前字符为'.'
                else if (dp[i - 1][j - 1] && p.charAt(j - 1) == '.') dp[i][j] = true;         // 2.
            }
        }
    }
    // 返回整个状态数组的最后一个值，即s是否能被p匹配
    return dp[m - 1][n - 1];
}

}
